package com.congee02;

import java.util.Arrays;

public class MaxSubArray_ML {

    public int maxSubArray(int... nums) {

        cache = new int[nums.length][nums.length];

        for (int[] e : cache) {
            Arrays.fill(e, -1);
        }

        process(nums, 0, nums.length - 1);
        return ans;
    }

    private int[][] cache;
    int ans = Integer.MIN_VALUE;
    private int process(int[] nums, int st, int ed) {
        if (st == ed) {
            ans = Math.max(ans, nums[st]);
            return nums[st];
        }
        if (cache[st][ed] == -1) {
            int p1 = process(nums, st + 1, ed) + nums[st];
            int p2 = process(nums, st, ed - 1) + nums[ed];
            cache[st][ed] = Math.max(p1, p2);
        }
        ans = Math.max(ans, cache[st][ed]);
        return cache[st][ed];
    }

}
